import java.util.Stack;

public class Trap {
    // leetcode 接雨水
    // https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked

    /**
     * 通过先遍历数组记录对应位置左边和右边的最高的柱子，然后就可以算出当前位置可以接的水的体积
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int n = height.length;
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (height[i] < max) {
                maxLeft[i] = max;
            }else {
                max = height[i];
            }
        }
        max = 0;
        for (int i = n-1; i >= 0; i--) {
            if (height[i] < max) {
                maxRight[i] = max;
            }else {
                max = height[i];
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.max(Math.min(maxLeft[i], maxRight[i])-height[i], 0);
        }
        return sum;
    }

    /**
     * 单调栈
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        Stack<Integer> stack  = new Stack<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            if (stack.isEmpty() || height[i] < height[stack.peek()]) {
                stack.add(i);
            }else {
                while (height[i] > height[stack.peek()]) {
                    int mid = stack.pop();
                    if (stack.isEmpty()) break;
                    int left = stack.peek();
                    sum += (Math.min(height[left], height[i])-height[mid]) * (i-left-1);
                }
                stack.add(i);
            }
        }
        return sum;
    }
}
